1. Field of the Invention
The present invention relates to method and apparatus for entropy coding and decoding.
2. Description of the Related Art
In entropy coding, it is necessary to obtain the coding probability of symbols to be coded. As a method of calculating a coding probability, there has been proposed a method of using a full tree (also called a context tree) which associates one-dimensional data sequences output in the past with paths from the leaf nodes to the root node. The method disclosed in F. M. J. Willems, Y. M. Shtarkov, and T. J. Tjalkens, “The Context Tree Weighting Method: Basic Properties”, IEEE Trans. Inform. Theory, vol. 41, no. 3, pp. 653-664, May 1995 is called a context-tree weighting (CTW) algorithm. It is known that using the coding probability calculation method disclosed in this reference and T. Matsushima and S. Hirasawa, “A Bayes Coding Algorithm for FSM Sources”, Proc. Int. Symp. on Information Theory pp. 388, September 1995 makes it possible to obtain a high coding efficiency with respect to a one-dimensional data sequence output of a Markov process.
Assume that two matrices, namely an information matrix as symbols to be coded and a reference matrix are given. In this case, as an application of entropy coding, it is conceivable to use a technique of coding or decoding components of an information matrix by using components of a reference matrix. When using a coding probability calculation method using a context tree for coding/decoding of matrix components in this manner, it is necessary to set a path from a leaf node of a context tree to a root node in accordance with the correlation between matrices. For example, regarding the pixel levels of two temporarily consecutive frames in a video sequence as an information matrix and a reference matrix, the correlation between a component of the information matrix and a component of the reference matrix generally increases with a decrease in the distance between the two matrix components. In this case, performing coding/decoding while associating a one-dimensional data sequence, in which a reference matrix is simply arranged in the raster scan order, i.e., the horizontal direction, with a path from a leaf node to a root node of a context tree amounts to performing coding/decoding without any consideration to the correlation between a component of an information matrix of interest and a component of a reference matrix arranged in the vertical direction. This is not preferable in terms of coding efficiency.